COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\\M1BASL30\M2BASB30\M3NGR25\M4NGR20\M5BASI30\F1
C00015 ENDMK
C⊗;
\\M1BASL30;\M2BASB30;\M3NGR25;\M4NGR20;\M5BASI30;\F1



\J
Let me give you a slight introduction to  the manuscript. It grew out
of  a course on data  structures I developed at  UCLA  
while teaching as an Assistant Professor in 1970-1972.
Many universities, UCLA included, present data-structure courses in their 
program
at a point when the typical student has no background for assessing
the importance of the techniques. Typically a book like Knuth's is
used. The difficulty is that a background in simple PL/1 or Fortran programming
offers no motivation for studying trees, hashing, garbage collection,
stacks, threading, or any of the other esoteric tricks. My contention is that
these techniques, present themselves very naturally in the
context of LISP and its implementation.
My second objection is the use of machine language for discussion
data-structure algorithms. We don't require machine language for numerical
analysis, so why not treat  non-numerical algorithms with the same respect?
LISP is a natural language for such discussions; it not a toy language, but
has a rich history of interesting programming examples.

Once motivation for the study and understanding of data structures is established,
then the techniques can be introduced easily in the context of implementation
of LISP. 
Indeed, many of the current tricks of software implementation find their origins
in LISP's implementation.
But even at this point  the appropriate level of abstractness
should be used. All of the data-structure techniques are best understood
at a level higher than machine language. When you want to implement a 
specific technique on a specific machine, then talk about efficiency
and bit-pushing. 

I taught five variants of this course at UCLA, each becoming more LISP
and less Knuth. Student reaction was quite good. I expanded and
revised the notes here at Stanford for a "reading and research  course",
and have taught variants  at the
UC Santa Cruz graduate  workshop the last  two years. I will  be helping
San  Jose State  set up their  graduate data  structures courses next
semester  and will  use  the  manuscript  there. 
I will be teaching their first data structures course in the
spring term. A  few  students  in
Stanford's CS206 course used the manuscript,  and some students  at 
the University of Utah
are currently using it.
The reaction from reviewers, both students  and the research community
has been quite favorable.

The manuscript will attempt to be self-contained because I think LISP
is the best way  to introduce prospective students to  the field. The
fewer preconceptions about  programming languages,  the better.  
LISP is an excellent way to take intelligent, but technically naive,
students rapidly to advanced topics in such a way that intuition and the 
continuity of Computer Science is maintained.
Thus
the book  goes  from very  basic  undergraduate material  to  current
research in semantics.  The material on λ-calculus and Scott's models
is  currently  very  rudimentary.   I  am  beginning  to  develop an
intuitive introduction to these areas.

Basically the material falls into  6 areas: 

	\F21.\F1 The mechanics  of the
language;  recursion,    functional  arguments.    Representation  of
algorithms in a  programming language, representation  of domains  as
data structures. 

	\F22.\F1 Evaluation; the importance  of interpretation and
its  relation  to  denotational models.   Scott's models and the λ-calculus.

	\F23.\F1 Implementation of the static structure of LISP and the
problems of machine orgainzation. 

	\F24.\F1 The dynamic structure of LISP and compilers for LISP;  LISP, being
a  very clean  way  to introduce  compilation.   

	\F25.\F1 Storage and efficiency; more detailed discussion of storage
management; arrays, strings, stacks. Tricks of LISP programming: rplaca and
rplacd. Efficiency: double linking, threading, fancy garbage collection....

	\F26.\F1 Implications  for
language  design; given a clear  understanding of LISP,   what can be
done better? Most of this  comes from  my own ideas  on a LISP-like  language
with  user-defined data  structures  and a  semantics  which is  more
amenable to proofs and verifications.
Besides my own ideas, this section will incorporate other more well-known
"extensions" of LISP ideas. Namely the two innovations deriving from PLANNER:
pattern directed invocation, and structured data bases. 


Now,   the state of the manuscript.  Parts  (1),  (2),  and (3) are in
reasonable  shape; perhaps  85%  complete.
Part (4), on compilers, perhaps 65% completed. 
Part (5) needs  some revison and additions.; it's perhaps 70% completed.
Part (6), though absent from the manuscript is at least 50% completed. 

The reviews have been quite favorable,   and I am convinced that  the
manuscript  should be  published.    LISP  is the  most  most  poorly
understood programming language around, and it gets a little tiresome
to see people re-inventing McCarthy's ideas simply because there's no
decent documentation.  

There's a succinct statement by Strachey which
reflects my attidude  about programming languages and the approach
advocated in the manuscript:
\F5"I
always worked on programming  languages because it seems to  me until
you  could  understand those,    you  couldn't understand  computers.
Understanding them doesn't really mean only being able to use them. A
lot of people  can use them  without understanding them."\F1. This quote
appears at the beginning of the chapter on evaluation!

The current manuscript represents a entensive revision of the past material,
incorporating many reviewer's suggestions, though no one has had a 
chance to see this new product.
 In all,  15-20 "people" have read parts of the
manuscript; enumerable "students" have made comments.


Now to more mundane matters. The text is machine-generated, including all
fonts and formatting information. Thus it is a simple job to
modify the manuscript to conform with publishing conventions. The
book could be photo-offset from such output or it seems quite feasible
to generate an output file which could be used to drive a type-setting
machine. In either case the publishing costs could be greatly reduced
from those experienced using the standard production techniques.

If you desire more information on the manuscript please call me at 497-4971.
\.



					John  Allen